/**
 * 
 */
package uk.ac.manchester.cs.graph;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;

/**
 * @author Pavel Klinov
 *
 * pklinov@cs.man.ac.uk, pklinov@clarkparsia.com
 * 
 * Dec 16, 2008
 * 
 * Used to store partially ordered elements in a SortedSet
 */
public class SortedSetImpl<T> implements SortedSet<T> {

	protected Set<T> m_set = null;
	protected List<T> m_items = null;
	protected Comparator<T> m_comparator = new ComparatorImpl();
	
	public SortedSetImpl() {
	
		m_set = new HashSet<T>();
		m_items = new ArrayList<T>();
	}
	
	public SortedSetImpl(Comparator<T> comparator) {
		
		this();
		
		m_comparator = comparator;
	}
	
	
	public SortedSetImpl(int size) {
		
		m_set = new HashSet<T>(size);
		m_items = new ArrayList<T>(size);
	}	
	
	public SortedSetImpl(int size, Comparator<T> comparator) {
		
		this(size);
		
		m_comparator = comparator;
	}
	
	
	public SortedSetImpl(Collection<? extends T> elems) {
		
		m_set = new HashSet<T>(elems);
		m_items = new ArrayList<T>(m_set);
		
		Collections.sort( m_items, m_comparator );
	}
	
	public SortedSetImpl(Collection<? extends T> elems, Comparator<T> comparator) {
		
		m_comparator = comparator;
		
		m_set = new HashSet<T>(elems);
		m_items = new ArrayList<T>(m_set);
		
		Collections.sort( m_items, m_comparator );
	}
	
	public Comparator<? super T> comparator() {

		return m_comparator;
	}

	public T first() {

		return m_items.get( 0 );
	}

	public SortedSet<T> headSet(T arg0) {

		throw new RuntimeException("Not yet implemented");
	}

	public T last() {

		return m_items.get( m_items.size() - 1 );
	}

	public SortedSet<T> subSet(T arg0, T arg1) {

		throw new RuntimeException("Not yet implemented");
	}

	public SortedSet<T> tailSet(T arg0) {

		throw new RuntimeException("Not yet implemented");
	}

	public boolean add(T elem) {

		boolean result = m_set.add( elem );
		
		if (result) {
			
			int index = Collections.binarySearch( m_items, elem, m_comparator );
			
			index = (index < 0) ? - index - 1 : index;
			
			if (index >= m_items.size()) {
				
				m_items.add( elem );
				
			} else {
				
				m_items.add( index, elem );
			}
		}
		
		return result;
	}

	public boolean addAll(Collection<? extends T> elems) {

		boolean result = false;
		
		for (T elem : elems) result |= add( elem );
		
		return result;
	}

	public void clear() {

		m_set.clear();
		m_items.clear();
	}

	public boolean contains(Object elem) {

		return m_set.contains( elem );
	}

	public boolean containsAll(Collection<?> elems) {

		return m_set.contains( elems );
	}

	public boolean isEmpty() {

		return m_set.isEmpty();
	}

	public Iterator<T> iterator() {

		return m_items.iterator();
	}

	public boolean remove(Object elem) {

		boolean result = m_set.remove( elem );
		T element = (T) elem;
		
		if (result) {
			
			int index = Collections.binarySearch( m_items, element, m_comparator );
			//There might be several items with the same index
			int remIndex = 0;
			
			if ((remIndex = searchAmidEquals(element, index, 1)) > 0) {
				
				m_items.remove( remIndex );
				
			} else {
				
				m_items.remove( searchAmidEquals(element, index, -1));
			}
		}
		
		return result;
	}
	
	private int searchAmidEquals(T elem, int index, int inc) {
		
		int hashCode = elem.hashCode();
		T current = null;
		
		while(index < m_items.size() &&
				m_comparator.compare((current = m_items.get( index )), elem) == 0) {
			
			if (hashCode == current.hashCode()) {
				
				return index;
			}
			
			index += inc;
		}
		
		return -1;
	}

	public boolean removeAll(Collection<?> elems) {

		boolean result = false;
		
		for (Object elem : elems) result |= remove( elem );
		
		return result;
	}

	public boolean retainAll(Collection<?> arg0) {

		throw new RuntimeException("Not yet implemented");
	}

	public int size() {

		return m_set.size();
	}

	public String toString() {
		
		return m_items.toString();
	}
	
	public Object[] toArray() {

		return m_items.toArray();
	}

	public <T> T[] toArray(T[] arr) {
		/*
		 * Copied from JDK 1.5
		 */
        int i = size();

		if( arr.length < i ) {

			arr = (T[]) Array.newInstance( ((T) (arr)).getClass().getComponentType(), i );
		}
		
		Iterator iterator1 = iterator();
		Object arr1[] = arr;

		for( int j = 0; j < i; j++ ) {
			
			arr1[j] = iterator1.next();
		}

		if( arr.length > i ) {
			
			arr[i] = null;
		}
		
		return arr;
	}

	class ComparatorImpl implements Comparator<T> {

		public int compare(T first, T second) {

			return ((Comparable<T>)first).compareTo( second );
		}
		
	}
}
